package com.hanxiaozhang.no10leetcode.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给两个整数n和k，从1到n中选择k个数字排列返回结果，对结果的顺序没有要求
 * 实例1:
 * 输入: n = 4, k = 2    -> 从[1,2,3,4]选2个数
 * 输出: [[1,2],  [1,3], [1,4], [2,3], [2,4], [3,4]]
 * 实例2:
 * 输入: n = 1, k = 1
 * 输出: [[1]]
 * <p>
 * 整体思路（灵魂）：
 * -- 每次递归选择一个数（这里需要循环选择一个数，处理每种情况），递归到结束条件时（结果个数等于k时），保存结果。
 * -- 每次递归后，需要恢复现场。
 * <p>
 * 具体步骤：
 * 构建一个递归方法：
 * -- 递归入参：需要技巧
 * --- results  结果
 * --- curResult  本次结果
 * --- arr   数组
 * --- k 剩余元素个数
 * --- start 开始选择元素位置
 * -- 逻辑：
 * --- 边界条件：k == 0 时，加入结果，注意 new ArrayList()
 * --- 循环：开始条件：start，结束条件：i < arr.length
 * ---- 每次循环 i. 添加元素 ；ii. 调用 backTrack(... k - 1, i + 1)； iii. 删除元素，恢复现场
 *
 * @author hanxinghua
 * @create 2024/2/6
 * @since 1.0.0
 */
public class No77Combinations {


    public static void main(String[] args) {

        System.out.println(method1(4, 2));

        System.out.println(method1(1, 1));

    }


    private static List<List<Integer>> method1(int n, int k) {

        List<List<Integer>> results = new ArrayList<>();
        if (n == 0 || k == 0 || k > n) {
            return results;
        }

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }

        // new ArrayList<>() -> 全局共用一个结果集。
        backTract(results, new ArrayList<>(), arr, k, 0);

        return results;
    }

    /**
     * 递归
     *
     * @param results   结果
     * @param curResult 本次结果
     * @param arr       数组
     * @param k         剩余元素个数
     * @param start     开始选择元素位置
     */
    private static void backTract(List<List<Integer>> results, List<Integer> curResult, int[] arr, int k, int start) {

        if (k == 0) {
            results.add(new ArrayList<>(curResult));
            return;
        }

        for (int i = start; i < arr.length; i++) {
            // 添加元素
            curResult.add(arr[i]);
            backTract(results, curResult, arr, k - 1, i + 1);
            // 删除元素，恢复现场
            curResult.remove(curResult.size() - 1);
        }
    }
}
